Clustering in WSN
A wireless sensor network (WSN) is composed of a large number of spatially distributed usually low-cost, low-power sensors collaborating to accomplish a common task and capable of short-range wireless communications over an area of deployment. Compared to traditional communication systems, WSNs may be characterized by the following: high deployment density (several orders of magnitude higher than mobile ad hoc network—MANET); low-power nodes (usually powered by battery, may be deployed in a harsh or hostile environments); no global identification (due to the large number of sensor nodes); relatively severe energy constraints, severe computation constraints, and severe storage constraints; and requiring topology changes, etc. See generally J. Zheng, A. Jamalipour, “Wireless Sensor Networks: A Networking Perspective”, John Wiley & Sons, 2009 (hereinafter Zheng), which is incorporated by reference in its entirety.
FIG. 1 illustrates an exemplary sensor network architecture 100. Sensors 101 (e.g., nodes) cooperate in order to transmit the sensed data via gateways and to make it available to wider networks such as the Internet 103, via one or more sinks 102 or base stations (BSs). The capability constraints of the sensor nodes (limited memory, processing power, energy supply, and bandwidth) combined with the typical deployments consisting of large numbers of nodes, pose many challenges to the design and management of such networks such as scalability and energy consumption. Solutions targeting this specific application have been developed to include energy awareness at different layers of the protocol stack and to affect some WSN aspects such as routing and topology.
Some WSN specific optimizations have departed from the use of Internet protocol (IP), considering that assignments and updates based on a global addressing scheme impose heavy overheads for large-scale WSN with dynamic and unpredictable topology changes, especially in a mobile environment. Optimizations also take in consideration the high probability of data redundancy, while providing mechanisms for timely delivery in time-constrained applications of WSNs. An additional consideration is that in many WSNs the communication burden may be heavily directional, from multiple sources to one particular sink, rather than multicast or peer to peer, while still requiring bi-directionality.
Non-IP WSNs deployments may employ flat or hierarchical topologies. Flat topologies are characterized by all nodes having similar properties and functions, and performing similar tasks at the network level. In this case all sensor nodes are peers. Without a global addressing scheme data gathering is usually accomplished through queries to all nodes via flooding.
FIG. 2A and FIG. 2B illustrate flat and cluster-based hierarchical WSN topologies. In the latter, topologies nodes perform different networking tasks and are typically grouped in clusters according to specific requirements or metrics. In cluster-based topologies the communications are encapsulated within the group and are addressed to a cluster head (CH).
Nodes with lower energy levels or more constrained resources may perform sensing tasks, with the resulting data being routed via CHs 105 and collected at a sink or base station (BS) 106. BSs 106 act as a gateway within the WSN and typically communicate with M2M servers. Within a cluster, BS 106 role is primarily a communication role, however BS 106 might be itself CH 105 (communicating directly with end nodes), may communicate only with CHs 105 (becoming a data sink) or both. In the cluster group belonging to a CH 105 some nodes may be CHs 105 coordinating other sub-clusters. FIG. 3 illustrates another exemplary cluster that includes elements such as CH, BS, and nodes (e.g., sensors, etc.).
Clusters may help support for data aggregation or fusion, scalability, load reduction, or energy savings. The cluster-based protocols take advantage of these unique characteristics to provide significant advantages over flat strategies. Many applications of WSNs such as environmental and natural phenomena monitoring, security control and traffic flow estimation, monitoring and tracking for military applications, rely on clustering techniques to increase network scalability and extend their lifetime.
Clustering Algorithms in WSN
Conventional clustering algorithms described in the reference literature are designed for cluster-based topology management to determine and optimize CH selection and at the same time to determine and optimize routing. A cluster protocol, as discussed herein, may be a particular implementation of a clustering algorithm. They have been designed specifically for the scalability and efficient communication within WSNs, and may involve one or multiple hop communication. Clustering may affect routing (e.g., when higher energy nodes are used for routing while the low energy nodes are used for sensing). Cluster based routing advantages may include higher scalability, employment of data aggregation/fusion, lower loads, and lower energy consumption.
There is extensive research work and literature addressing clustering protocol designs and demonstrating the need for optimization of the communication protocols in WSN, and of clustering protocols in particular. A considerable number of novel schemes have been proposed, compared and surveyed. The following are references that contain multiple examples: 1) Atul Pratap Singh, Nishu Sharma; “The Comparative Study Of Hierarchical Or Cluster Based Routing Protocol For Wireless Sensor Network” , International Journal of Engineering Research & Technology (IJERT), Vol. 2 Issue 6, June—2013 (hereinafter Singh); 2) Liliana M. Arboleda C. and Nidal Nasser: “Comparison of clustering algorithms and protocols for wireless sensor networks” (hereinafter Arboleda); 3) Ameer Ahmed Abbasi, Mohamed Younis, “A survey on clustering algorithms for wireless sensor networks”, Computer Communications 30 (2007) 2826-2841 (hereinafter Abbasi); and 4) Xuxun Liu, “A Survey on Clustering Routing Protocols in Wireless Sensor Networks”, Sensors 2012 (hereinafter Liu). The examples are incorporated by reference in their entirety.
The variety reflects a wide range of approaches as well as considerable variations in the problems proposed and the framework for analysis and modeling. Each clustering algorithm optimizes based on a specific context created by the network models, by the clustering process attributes and with specific optimization objectives.
Network models considered when selecting a clustering algorithm reflect characteristics of the given network and its individual nodes. For example, considerations may include the following:                Node capabilities (at various levels: BS, CH, end-nodes)                    Mobility: stationary/mobile/re-locatable (which may be different by level BS/CH/sensor)            Resources (e.g., computational, memory, etc.): constrained or rich            Role: relaying/sink/data aggregation/sensing, etc.            Diversity: homogeneous vs. heterogeneous (for whole network or at CH level only)                        Clustering attributes:                    Cluster count: preset/variable            Cluster size: preset/variable            Topology: fixed/adaptive            CH to BS connectivity: provisioned/assumed            Routing capabilities: singe or multi-hop.            Re-clustering methodology: periodic/event based/etc.                        
Clustering process attributes are mainly related to procedural aspects of the algorithm such as:                Proactivity: Proactive/Reactive/Hybrid        Clustering methodology: Distributed/Centralized/Hybrid        CH selection: Random/Adaptive/Deterministic        Algorithm complexity        Convergence time: Fixed/Variable        Execution type: Probabilistic/Iterative        Cluster overlap: None/Low/High        
It should be noted that many of the characteristics noted above are tightly coupled and as such the compartmentalization of the attributes is not meant to be static and it certainly varies in the referenced literature. For example, the adaptive, deterministic or random nature of the CH selection process is strongly related to the overall node characteristics and especially those of the CHs, as well as to the level of heterogeneity present in the given network. Similarly cluster overlap is a process attribute which may be dictated by the network model and enforced in algorithm selection.
Optimization objectives (e.g., goals) of the individual clustering algorithms may include energy efficiency, load balancing, fault tolerance, increased connectivity and reduced delay, minimal cluster count, maximal network longevity, maximal residual energy, and quality of service.
Clustering algorithm designs tout a variety of advantages over flat routing in single or multi-hop networks, as provided in Liu. Examples may include lower latencies and energy consumption, collision avoidance, data aggregation/fusion, increased robustness and network lifetime, fault-tolerance, better guarantee of connectivity, and energy-hole avoidance, among other things. These advantages add to the optimization objectives a number of qualitative improvements, which may not always be the goal behind the choice of a specific algorithm.
Herein, the use of the term “optimization objectives” refers to the features of the algorithm for which there are specific methods to determine if the network optimization objectives are achieved. For example, it has been determined that LEACH achieves the optimization objective of minimizing global energy usage in comparison to a minimum transmission routing (MTE) system for a network model of randomly positioned sensors with short communication distances, where randomization of the CH among the nodes is possible. See generally W. Heinzelman, A. Chandrakasan and H. Balakrishnan, “Energy-efficient communication protocol for wireless microsensor networks”, Proceedings of the 33rd Annual Hawaii International Conference on System Sciences, 2000, no. 10, vol. 2, January 2000 (hereinafter Heinzelman), which is incorporated by reference in its entirety. In order to make this determination “optimization metrics” such as the energy dissipated, system lifetime and number of nodes alive after a certain number of iterations have been quantified and evaluated. Qualitative optimization objectives may include the ability to obtain sensed information in specific query formats, but, in the end, all such requirements provides for avenue of quantification in order to provide system improvements. The term “conventional algorithm metric,” as used herein, denotes the attributes used by a conventional clustering algorithm to operate, such as the received power and a node's own energy level for LEACH.
Tables below have been compiled by experts and presented in surveys or comparison papers. The information of Tables 1-3 provide quick overviews of the characteristics, advantages, and disadvantages presented by each reviewed algorithm.
TABLE 1Clustering Algorithms—advantages and disadvantages (See Singh)EnergyLoadDeliveryProtocolEfficiencybalancingDelayAdvantagesDisadvantagesLEACHVery lowMediumVeryEach node equallyNot applicable forsmallshares the load and large region,TDMA scheduleEnergy is notprevents CHs fromconsidered for Clusterunnecessaryhead selection andcollisions.dynamic clusteringbrings extra overhead.HEEDMediumMediumMediumFully distributedUnbalanced energyclustering method,consumption, overheadMulti-hop routing,of cluster headuniform CHselection in each roundselection, moreand CH near to theenergybase die soon becauseconservation andof extra work load.long rangecommunication.DWECHVery highVeryMediumFully distributedSingle-hopegoodclustering method,communication, notConsider energyapplicable for largefor CH selectionregion and high controland clusteringmessage overhead.process ofterminates in a fewiterations.TL-LowBadSmallBetter energy loadNot applicable forLEACHdistribution,large regions, energy islocalizednot considered for CHcoordination andselection and bad loadreduces the totalbalancing.energyconsumption.UCSVery lowBadSmallMore uniformIt lacks universality,energyresidual energy notconsumptionconsider for CHamong the CHsselection and still notand two-hopapplicable for largecommunicationregion.method.EEUCHighMediumMediumAn unequalSignificant overhead,clusteringextra global datamechanism toaggregation and Thebalance the energyrouting scheme canconsumptionresult in new hot spots.among CHs, multi-hop routingmechanism.BCDCPVery lowGoodSmallEnsures similarWorse scalability andpower dissipationrobust to largeof CHs control bynetworks, more designBS. Allows sensorcomplexity and morenodes to openenergy consumption.communicationSingle hop routing andinterfacesnot suitable forreactive networkPEGASISLowMediumVeryIt reduces theUnsuitable forlargeoverhead ofnetworks with a timedynamic clustervarying topology, notformation,suitable for largedecreases datanetwork, large delaytransmissionand difficult tovolume throughmaintenance database.the chain of dataaggregation andThe energy load isdisperseduniformlyTEENVery highGoodSmallTwo thresholdsNot suitable forreduces the energyperiodic reportstransmissionapplication, the BS mayconsumption andnot be able tosuitable for reactivedistinguish dead nodesscenes and timefrom alive ones andcriticaldata may be lost.applications.APTEENMediumMediumSmallSuitable for bothHigh overheadproactive andcomplexity for designreactiveand implementation ofapplication andcluster construction inflexibility bymultiple levels.setting the count-time interval forcontrol the energyconsumption.CCSLowVery badLargeMulti-hop routing,Node distribution ina considerableeach level isamount of energyunbalanced, Residualis also conservedenergy is notduring dataconsidered for CHtransmission.election, long chainwould cause large delay
TABLE 2Clustering Algorithms—differentiation criteria (See Arboleda)Cluster NetworkSensorsSensorsClusteringHeadTypeMobilityTypeProcessElectionClustering FormationPro-Re-Homo-Hetero-AttributeCentra-Distri-activeactiveStationaryMobilegeneousgeneousStaticDynamicFixedRandomBasedlizedbutedFixedDCATTXXXPartiallyXPartiallyLEACHXXPartiallyXXXXLEACH-CXXPartiallyXXXXLEACH-FXXXXXXXTEENXXPartiallyXXXXAPTEENXXPartiallyXXXXHEEDXPartiallyPartiallyXXXXEECSXXXXXXSensorXXXXXXAggregation ACEXXXXXXCAGXXXXXXUpgradedXXXXXXCAGEEDCXXXXXXTASCXXXXXX
TABLE 3Clustering Algorithms—differentiation in applicability (See Abbasi)ClusteringConvergenceNodeClusterLocationEnergy FailureBalanced ClusterapproachestimemobilityoverlappingawarenessefficientrecoveryclusteringstabilityLCAVariablePossible NoRequiredNoYesOKModerateO(n)AdaptiveVariableYesNoRequiredN/AYesOKLowclusteringO(n)CLUBSVariablePossible HighNotN/AYesOKModerateO(n)requiredHierarchicalVariablePossible LowNotN/AYesGoodModeratecontrolO(n)requiredclusteringRCCVariableYesNoRequiredN/AYesGoodModerateO(n)GS3VariablePossible LowRequired N/AYesGoodModerateO(n)EEHCVariableNoNoRequired YesN/AOKN/AO(k1 + k2 + . . . + kh)LEACHConstantFixed BS NoNotNoYesOKModerateO(1)requiredFLOCConstantPossible NoNotN/AYesGoodHighO(1)requiredACEConstantPossible Very LowNotN/AYesGoodHighO(d)requiredHEEDConstantStationaryNoNotYesN/AGoodHighO(1)requiredExtendedConstantStationaryNoNotYesN/AVeryHighHEEDO(1)requiredgoodDWEHCConstantStationaryNoRequired YesN/AVeryHighO(1)goodMOCAConstantStationaryYesNotYesN/AGoodHighO(1)requiredAttribute-ConstantNoNoRequired YesYesVeryHighbasedO(1)goodclustering
Herein the term “conventional clustering functionality” is used to encompass all the lower layer functionality which traditionally accomplishes the clustering operations (e.g., CH assignment/re-assignment, routing, or topology management).
There are different views of the WSN protocol stack. Conventionally, the most common follow the layered models in the traditional protocol stacks and comprise of Application, Transport, Network, Data Link, and Physical layers. The WSN-specificity is reflected in the delineation of vertical/functional planes focused on providing Task, Connection, and Power Management, as shown in FIG. 4.
Other WSN-specific optimizations have resulted in proposals such as the unified Cross-Layer Module XLM. See generally I. F. Akyldiz, I. F., M C. C. Vuran and O. B. Akan. “A cross layer protocol for wireless sensor networks.” Proc. Conference on Information Sciences and Systems (CISS'06) (2006): 1102-1107 (hereinafter Akyldiz), which is incorporated by reference in its entirety. FIG. 5 illustrates XLM cross layer module vs. the WSN layered model. The XLM cross layer module is designed to optimize overall energy expenditure in the WSN and to achieve efficient and reliable event communications. A single cross-layer module for resource-constrained sensor nodes merges the traditional protocol layer entities, while keeping the operations distributed and adaptive. The conventional clustering algorithms in this context are implemented within the XLM Cross-Layer module.
FIG. 6A-FIG. 6C are exemplary illustrations of protocol stack models and mapping of the conventional clustering functionality for TCP/IP, WSN, and WSN cross layer model. Based on the WSN protocol model of FIG. 4 the conventional clustering functionality as disclosed herein maps to the transport, network, data link and physical layers as depicted in FIG. 6B, and may be mapped to the Connection Management Plane in FIG. 4. Although the WSN Protocol model depicted is widely recognized in literature, the “Management Planes” tend to differ depending on authors and are not standardized. They are a reflection of the WSN-specific tasks which in fact drive the effort for optimizations in this domain.
FIG. 6A-FIG. 6C also depicts the parallels between the TCP/IP and the WSN protocol models. The WSN stack is used for intra-cluster communications and as such is supported by sensors, CHs, BSs, and other nodes. Usually the WSN is connected to larger networks such as the Internet as shown in FIG. 1. Nodes which are part of WSN, but at the same time provide gateway functionality (e.g., BS, CH), support dual stacks, which integrates the WSN with networks using the Internet protocol family.
The conventional clustering algorithms enumerated herein (e.g., Table 1-Table 3) and described in the reference material have a number of common attributes. A first attribute is that conventional clustering algorithms are designed for cluster-based topology management, to determine and optimize CH selection and at the same time to determine and optimize routing. The optimization portion of each algorithm provides re-clustering. Some algorithms specify cluster-based in-network data processing such as aggregation and fusion.
A second attribute is that conventional clustering algorithms are adaptive within their given optimization goal. For example, in DWEHC the CHs are chosen using metrics for expected residual energy which is considered a function of distance between nodes. Should this scheme prove to be inefficient, for example, because the energy expanded on non-communication tasks is more significant, the algorithm cannot be changed to be based on an abstract metric such as capability grade. See generally P. Ding, J. Holliday and A. Celik, “Distributed Energy Efficient Hierarchical Clustering for Wireless Sensor Networks”, Proc. The IEEE International Conference on Distributed Computing in Sensor Systems 2005, Marina Del Rey, Calif., (2005), pp. 322-339 (hereinafter Ding), which is incorporated by reference in its entirety. “Capability grade” is an attribute used by algorithms such as C4SD and is based on node characteristics such as device hardware and firmware capabilities. See generally R. S. Marin-Perianu, J. Scholten, P. J. M. Havinga and P. H. Hartel, “Cluster-based service discovery for heterogeneous wireless sensor networks”, International Journal of Parallel, Emergent and Distributed Systems, 2008 (hereinafter Marin-Perianu), which is incorporated by reference in its entirety.
A third attribute is that conventional clustering algorithms are designed to be implemented below the Application Layer. Some protocol designs adapted WSN present differentiated application protocol and service layers, as shown in FIG. 6B. The application protocol layer may use protocols such as HyperText Transfer Protocol (HTTP) or Constrained Application Protocol (CoAP) and may have functions such as messaging and congestion control. The Service Layer (SL) may support functions such as data collection, device management, security, etc. which are provided as services to the application layer. Other modeling methodologies (e.g. XLM cross-layer module (Akyldiz)) combine functionality from two or more layers in cross-layer designs, as shown in FIG. 6C.
A fourth attribute is that conventional clustering algorithms use information available below the Application Layer for optimization, and as such service layer (SL) information is unavailable. In order to preserve the functionality of the layered model, these conventional clustering algorithms have been designed to use information available within their own layer, which is normally the Network/Routing layer. Even in cross-layer designs the information used for clustering optimization is the one available below the Application Layer.
Service Layer in M2M Communications
The oneM2M standard (oneM2M-TS-0001 oneM2M Functional Architecture-V-1.6.1, which is incorporated by reference in its entirety) under development defines a service layer called common service entity (CSE), as illustrated in FIG. 7. Mca reference point 111 interfaces with application entity (AE) 112. Mcc reference point 113 interfaces with another CSE 115 within the same service provider domain and Mcc' reference point 116 interfaces with another CSE (not shown) in a different service provider domain 117. Mcn reference point 118 interfaces with the underlying network service entity (NSE) 119. NSE 119 provides underlying network services to the CSEs, such as device management, location services and device triggering. CSE contains multiple logical functions called “Common Service Functions (CSFs)”, such as “Discovery” or “Data Management & Repository.”
In M2M communications the service layer (SL) aims to enable platforms for delivery of third-party value-added services and applications by supporting secure end-to-end data/control exchange between M2M devices and customer applications and to provide capabilities for remote provisioning & activation, authentication, encryption, connectivity setup, buffering, synchronization, aggregation and device management. SL provides interfaces to the underlying networks and may enable capabilities using servers owned by service providers (SP) accessed through third-party content providers through application programming interfaces (APIs), for example.
An M2M/IoT service layer is specifically targeted towards providing value-added services for M2M/IoT type devices and applications. Standardization bodies such as ETSI M2M and oneM2M are developing M2M service layers specifically targeting sensor and device networks. Device Management (DM) is among the value-added services targeted by most SL platforms in order to provide solutions for issues such as firmware and software management, security and access control, device monitoring and logging, etc.
The oneM2M architecture is based on a Common Services Entity (CSE) which can be hosted on different types of network nodes in a network (e.g. infrastructure node, middle node, application-specific node).
Within the oneM2M RESTful architecture, (also known as resource oriented Architecture or RoA) the CSE supports the instantiation of a set of common service functions (CSFs), as shown in FIG. 8. CSF functionality is implemented via resources which are uniquely addressable entities having a representation that can be manipulated via RESTful methods such as Create, Retrieve, Update, and Delete. These resources are addressable using universal resource identifiers (URIs). A resource supports a set of attributes that store relevant information about the resource and may contain references to other resources termed child resources(s). A child resource is a resource that has a containment relationship with a parent resource and whose lifetime is limited by the resource lifetime of the parent.
oneM2M is providing specifications using a service oriented architecture (SoA) approach in addition to the RoA architecture introduced. See generally Service Component Architecture” oneM2M-TS-0007, oneM2M Service Component Architecture-V-0.6.0, which is incorporated by reference in its entirety. The SoA architectural concept is based on considering as building blocks the functionality provided by distinct software modules and known as services. Services are provided to applications via the specified interfaces which are independent of vendor, product or technology. The SoA representation of a CSE 121 in oneM2M is shown in FIG. 9.
From a deployment perspective, FIG. 10 depicts configurations supported by the oneM2M architecture. oneM2M architecture enables the application service node (ASN), application dedicated node (ADN), the middle node (MN), and the infrastructure node (IN). The ASN is a node that contains one CSE and contains at least one AE. An example of physical mapping is an ASN residing in an M2M Device. The ADN is a node that contains at least one AE and does not contain a CSE. An example of physical mapping is an ADN residing in a constrained M2M Device. An MN is a node that contains one CSE and contains zero or more AEs. An example of physical mapping for an MN is an MN residing in an M2M Gateway. The IN is a node that contains one CSE and contains zero or more AEs. An example of physical mapping for an IN is the IN residing in an M2M Service Infrastructure. There also may be a non-oneM2M node, which is a node that does not contain oneM2M Entities (neither AEs nor CSEs). Such nodes represent devices attached to the oneM2M system for interworking purposes, including management.
Reprogramming in WSN
Sensor network deployments should be designed with the ability to perform software and firmware maintenance without having to physically reach each individual node. The widespread adoption of mobile devices in recent years has led to great advances in the field of mobile device management (DM). While many DM methods address resource rich devices such as mobile phones, some protocols and methods, such as LWM2M (see Marin-Perianu), provide solutions for constrained devices. Related issues are under active evaluation in other standardization bodies. See generally M. Ersue, D. Romascanu, J. Schönwälder, “Management of Networks with Constrained Devices: Problem Statement and Requirements” IETF Draft, URL: https://datatracker.ietforg/doc/draft-ersue-opsawg-coman-probstate-reqs/, which is incorporated by reference in its entirety. The research community is also addressing such methods with specific interest in methods targeted to multi-hop code distribution systems wireless sensor networks. See generally 1) B. Hemappa, B. T. Shylaja, D. H. Manjaiah, B. Rabindranath, “An Energy Efficient Remote Data Collection and Reprogramming of Wireless sensors Networks” International Journal of Computer Trends and Technology, volume 3, Issue 3, 2012 (hereinafter Hemappa); and 2) T. Stathopoulos, J. Heidemann, D. Estrin, “A Remote Code Update Mechanism for Wireless Sensor Networks” CENS Technical Report #30, Center for Embedded Networked Sensing, UCLA, Los Angeles, Calif., USA, 2003 (hereinafter Stathopoulos). Hemappa and Stathopoullos are incorporated by reference in their entirety.